// https://leetcode.cn/problems/palindrome-partitioning-ii/description/

// 算法思路总结：
// 1. 使用动态规划预处理所有回文子串
// 2. dp[i][j]表示s[i..j]是否为回文串
// 3. count[i]表示s[0..i]的最小切割次数
// 4. 如果s[0..i]是回文则不需要切割，否则在前面的切割点后寻找回文段
// 5. 时间复杂度：O(n²)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int minCut(string s) 
    {
        int m = s.size(), ret = 0;
        vector<vector<bool>> dp(m, vector<bool>(m, false));

        for (int i = m - 1; i >= 0; i--) 
        {
            for (int j = i; j < m; j++) 
            {
                if (s[i] == s[j]) 
                {
                    if (i == j)
                        dp[i][j] = true;
                    else if (i + 1 == j)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }

        vector<int> count(m, INF);
        for (int i = 0 ; i < m ; i++)
        {
            if (dp[0][i]) 
            {
                count[i] = 0;
                continue;
            }
            for (int j = 0 ; j < i ; j++)
            {
                if (dp[j + 1][i])
                {
                    count[i] = min(count[i], count[j] + 1);
                }
            }
        }

        return count[m - 1];
    }
};

int main()
{
    string s1 = "aab", s2 = "ab";
    Solution sol;

    cout << sol.minCut(s1) << endl;
    cout << sol.minCut(s2) << endl;

    return 0;
}